package com.ruoyi.common.core.utils;


import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        //1.平方和
        /*
        Scanner scanner = new Scanner(System.in);
        double n = scanner.nextInt();
        int m = scanner.nextInt();
        double res = 0;
        scanner.nextLine();
        for (int i = 0; i < m; i++) {
            res += n;
            n = Math.sqrt(n);
        }
        System.out.println(String.format("%.2f",res));*/

        //2.水仙花数
        /*
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(),n = scanner.nextInt();
        int count = 0;
        scanner.nextLine();
        for (int i = m; i <= n; i++) {
            int q = i/100;
            int s = (i - q*100)/10;
            int g = i - q*100 - s*10;
            if (Math.pow((double) q,3) + Math.pow((double) s,3) + Math.pow((double) g,3) == i){
//            if (q*q*q + s*s*s + g*g*g == i){
                count++;
                System.out.printf(i + " ");
            }
        }
        if (count == 0){
            System.out.println("no");
        }*/

        //美团2021校招笔试-编程题(通用编程试题,第10场)
        //3.公司食堂
        /*
//        Scanner scanner = new Scanner(System.in);
//        int T = scanner.nextInt();//数据组数
//        for (int i = 0; i < T; i++) {
//            int table = scanner.nextInt();
//            String table_info = scanner.next();
//            int m = scanner.nextInt();
//            String people = scanner.next();
//            int[] solution = solution(table_info, people);
//            for (int res : solution) {
//                System.out.println(res);
//            }
//        }
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(reader.readLine());
        for (int i = 0; i < T; i++) {
            int table = Integer.parseInt(reader.readLine());
            String table_info = reader.readLine();
            int m = Integer.parseInt(reader.readLine());
            String people = reader.readLine();
            int[] solution = solution(table_info, people);
            for (int res : solution) {
                writer.write(Integer.toString(res));
                writer.newLine();
            }
        }
        writer.flush();
    }

    public static int[] solution(String table_info, String people){
        PriorityQueue<Integer> table_0 = new PriorityQueue<>(); //存储桌号
        PriorityQueue<Integer> table_1 = new PriorityQueue<>();
        PriorityQueue<Integer> table_2 = new PriorityQueue<>();
        for (int i = 0; i < table_info.length(); i++) {
            if (Integer.parseInt(table_info.charAt(i) + "") == 0){
                table_0.add(i + 1);
            } else if (Integer.parseInt(table_info.charAt(i) + "") == 1) {
                table_1.add(i + 1);
            }else {
                table_2.add(i + 1);
            }
        }
        int[] res = new int[people.length()];
        for (int i = 0; i < people.length(); i++) {
            if (people.charAt(i) == 'M'){
                Integer p;
                if (!table_1.isEmpty()){
                    p = table_1.poll();
                    table_2.add(p);
                }else {
                    p = table_0.poll();
                    table_1.add(p);
                }
                res[i] = p;
            }else {
                Integer p;
                if (!table_0.isEmpty()){
                    p = table_0.poll();
                    table_1.add(p);
                }else {
                    p = table_1.poll();
                    table_2.add(p);
                }
                res[i] = p;
            }
        }
        return res;*/

        //美团2021校招笔试-编程题(通用编程试题,第9场)
        //1.糕点
        /*
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int[] arr = new int[m];
            for (int i = 0; i < m; i++) {
                arr[i] = scanner.nextInt();
            }
            if (a > b) {
                int tamp = a;
                a = b;
                b = tamp;
            }
            int MAX = Integer.MIN_VALUE;
            int MIN = Integer.MAX_VALUE;
            for (int i = 0; i < m; i++) {
                MAX = Math.max(arr[i], MAX);
                MIN = Math.min(arr[i], MIN);
            }
            int remain = n - m;
            boolean flag = false;
            if (remain == 0 && a == MIN && b == MAX) {
                flag = true;
            } else if (remain == 1 && (a == MIN || b == MAX)) {
                flag = true;
            } else if (remain >= 2 && MIN >= a && MAX <= b) {
                flag = true;
            }
            if (flag) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        //2.晋级人数
        /*
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        int limit = arr[arr.length - x];
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] != 0 && arr[i] >= limit){
                res++;
            }
        }
        System.out.println(res);*/

        //3.回转寿司
        /*
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 0; i < T; i++) {
            int N = scanner.nextInt();
            int[] arr = new int[N];
            for (int j = 0; j < N; j++) {
                arr[j] = scanner.nextInt();
            }
            //常规情况
            int[] MAX_SUM = new int[N];
            MAX_SUM[0] = arr[0];
            int MAX = Integer.MIN_VALUE;
            for (int j = 1; j < N; j++) {
                MAX_SUM[j] = MAX_SUM[j-1] > 0 ? MAX_SUM[j-1] + arr[j] : arr[j];
                MAX = Math.max(MAX_SUM[j], MAX);
            }
            //子数组包含首尾相连
            int MIN = Integer.MAX_VALUE;
            int[] MIN_SUM = new int[N];
            MIN_SUM[0] = arr[0];
            for (int j = 1; j < N; j++) {
                MIN_SUM[j] = MIN_SUM[j-1] < 0 ? MIN_SUM[j-1] + arr[j] : arr[j];
                MIN = Math.min(MIN_SUM[j],MIN);
            }
            int sum = 0;
            for (int j = 0; j < N; j++) {
                sum += arr[j];
            }
            if (sum - MIN >MAX){
                System.out.println(sum - MIN);
            }else {
                System.out.println(MAX);
            }
        }*/
        //网易2021校招笔试-Java开发工程师（正式第二批）
        //1.项目经理
        /*
        Scanner scanner = new Scanner(System.in);
        String[] Id_A = scanner.next().split(" ");
        String[] Id_B = scanner.next().split(" ");
        while (scanner.hasNext()){

        }
        //2.电影院选座
        /*
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(" ");
        int[] arr = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            arr[i] = Integer.parseInt(s[i]);
        }
        List<Integer> list = new ArrayList<>();
        int count_l = 0,count_r = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0){
                int l = i,r = i;
                count_l = 0;
                while (arr[l] != 1 && l > 0){
                    l--;
                }
                if (l != 0 || arr[l] == 1){
                    count_l = i-l;
                }
                count_r = 0;
                while (arr[r] != 1 && r < arr.length - 1){
                    r++;
                }
                if (r != arr.length - 1 || (r == arr.length - 1 && arr[r] == 1)){
                    count_r = r - i;
                }
                if (count_l == 0){
                    list.add(count_r);
                } else if (count_r == 0) {
                    list.add(count_l);
                }
                list.add(Math.min(count_l,count_r));
            }
        }
        Collections.sort(list);
        System.out.println(list.get(list.size() - 1));*/

        //1.烤串
        /*
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String A = scanner.next();
        String B = scanner.next();
        StringBuilder sbd = new StringBuilder();
        for (int i = 0; i < n; i++) {
            String s1 = A.substring(i, i + 1);
            String s2 = B.substring(i, i + 1);
            sbd.append(s1 + s2);
        }
        System.out.println(sbd.toString());*/


        //2.定位
        /*
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); //棋盘边长
        List<int[]> detectorLoc = new ArrayList<>();
        List<int[]> correctPoint = new ArrayList<>();
        //写一个求出任意两点距离的辅助函数（某点坐标数组，目标点坐标数组） distance
        int target_x = 0,target_y = 0;
        for (int i = 0; i < 3; i++) {
            int[] detector = new int[]{scanner.nextInt(),scanner.nextInt()}; //每个探测器的坐标
            detectorLoc.add(detector);
        }
        int[] distanceLength = new int[n];
        for (int i = 0; i < 3; i++) {
            distanceLength[i] = scanner.nextInt(); //到每个探测器的目标距离
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (distance(new int[]{i, j}, detectorLoc.get(i - 1)) == distanceLength[i-1] && distance(new int[]{i, j}, detectorLoc.get(i - 2)) == distanceLength[i-2]
                && distance(new int[]{i, j}, detectorLoc.get(i - 3)) == distanceLength[i-3]){
                    correctPoint.add(new int[]{i,j});
                }
            }
        }


        int minx=Integer.MAX_VALUE,miny=Integer.MAX_VALUE;
        for (int[] re : correctPoint) {
            minx = Math.min(minx, re[0]);
        }
        for (int[] re : correctPoint) {
            if (re[0] == minx){
                miny = Math.min(miny, re[1]);
            }
        }
        System.out.printf("%d",minx);
        System.out.printf("%d",miny);*/

        //3.复习
        /*
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        double[] p = new double[n];
        double[] scr = new double[n];
        for (int i = 0; i < n; i++) {
            p[i] = (double) scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            scr[i] = (double) scanner.nextInt();
        }
        double[] res = new double[n];
        double[] scr1 = scr;
        Arrays.sort(scr1);
        double result = 0,limit = 0;
        for (int i = n-m; i < n; i++) {
            if (i == n-m){
                limit = scr1[i];
            }
            result += scr1[i];
        }
        for (int i = 0; i < n; i++) {
            if (scr[i] >= limit){
                continue;
            }
            double per = 100.00;
            res[i] = p[i]/per * scr[i];
            result += res[i];
        }
        System.out.println(String.format("%.2f",result));*/

        //1.三元组
        /*
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i+1; j < n-1; j++) {
                if (arr[i] <= arr[j]){
                    continue;
                }
                for (int k = j+1; k < n; k++) {
                    if (arr[i] == arr[k] && arr[i] > arr[j]){
                        count++;
                    }
                }
            }
        }
        System.out.println(count);*/

        //2.位数删除
        /*
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        String stra = String.valueOf(a);
        String strb = String.valueOf(b);
        int count = 0;
        if (a%b == 0 || b%a == 0){
            System.out.println(0);
        }
        */

        //3.长城

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        int top = arr[n-1];
        int sub = 0;
        for (int i = n-2; i > 0; i--) {
            if (arr[i] < top){
                sub = arr[i];
                break;
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
        }
        double sum_double = sum;
        int avr = (int) Math.round(sum_double/ (double) n);
        if (sub > avr){ //次高为sub
            //起伏
            for (int i = 0; i < n; i++) {
                if (i%2 == 0) { //第一个为波峰
                    while (arr[i] < top) {
                        arr[i] += 1;
                        count++;
                    }
                }else {
                    while (arr[i] < sub) {
                        arr[i] += 1;
                        count++;
                    }
                }

            }
        }else {  //次高为avr
            //起伏
            for (int i = 0; i < n; i++) {
                if (i%2 == 0) { //第一个为波峰
                    while (arr[i] < top) {
                        arr[i] += 1;
                        count++;
                    }
                }else { //第一个为波谷
                    while (arr[i] < avr) {
                        arr[i] += 1;
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
    /*
    public static int distance(int[] point,int[] targetPoint){
        return Math.abs(point[0] - targetPoint[0]) + Math.abs(point[1] - targetPoint[1]);
    }*/




}
